Choe Ryong-hae sinh ra tại huyện Sinchon, tỉnh Nam Hwanghae, ngày 15 tháng 1 năm 1950, là con trai của Choe Hyon, người từng là Bộ trưởng quốc phòng của Cộng hòa Dân chủ Nhân dân Triều Tiên 1968-1976. Ông gia nhập Quân đội nhân dân Triều Tiên vào năm 1967 và tốt nghiệp Đại học Tổng hợp Kim Il-sung chuyên ngành chính trị và kinh tế.

Năm 1980 ông đảm nhiệm chức vụ trong Ủy ban Trung ương đồng minh Thanh niên Xã hội Lao động chủ nghĩa xã hội chỉ đạo việc giáo dục tại nước ngoài. Năm 1981 làm Phó Chủ tịch Ủy ban Trung ương đồng minh Thanh niên Xã hội Lao động chủ nghĩa xã hội. Tháng 8 năm 1986 làm Chủ tịch Ủy ban Trung ương đồng minh Thanh niên Xã hội Lao động chủ nghĩa xã hội cho đến khi đổi tên thành Đoàn Thanh niên XHCN Kim Nhật Thành(1996),kiêm Phó Chủ tịch Hội nghị Nhân dân Tối cao, Thường nhiệm Ủy viên Hội nghị Nhân dân Tối cao, Ủy viên Trung ương Đảng.Năm 1990 ông đứng đầu Hiệp hội Bóng đá và Taekwando của Đoàn thanh niên Triều Tiên, vào năm 1993 được trao danh hiệu Anh hùng của Cộng hòa Dân chủ Nhân dân Triều Tiên.Ông bị mất chức Chủ tịch Đoàn thanh niên Ri Il-hwan kế nhiệm tại kỳ họp thứ 14 Trung ương Đoàn (1/1998).

Sau khi rời khỏi đoàn Thanh niên, Choe Ryong-hae làm Phó Trưởng ban Các vấn đề chung thuộc Ủy ban Trung ương Đảng, sau đó làm bí thư tỉnh Hwanghae từ 2006 tới 2010. Tháng 9 năm 2010, Tại Hội nghị lần thứ ba của Đảng, ông được phong hàm cấp Tướng đồng thời là thành viên của Ban Bí thư và Ủy ban Quân sự Trung ương, thành viên dự khuyết Bộ Chính trị. Ông cũng được bổ nhiệm làm Bí thư phụ trách vần đề quân sự.

Ông không được biết đến sau cái chết của Kim Jong-il. Ông được xem là cánh tay đắc lực của Kim Jong-un. Vào tháng 4 năm 2012 ông được thăng hàm lên Phó Soái, được vào Ủy ban Thường vụ (Đoàn chủ tịch) Bộ Chính trị, Phó Chủ tịch Ủy ban Quân sự Trung ương, Chủ nhiệm Tổng cục Chính trị Quân đội Nhân dân Triều Tiên phần lớn chức vụ được cho là để thay thế Jo Myong Rok sau cái chết của ông.

Được xem là cộng sự thân tín của Jang Song-thaek, sau đó là thành viên trong việc khôi phục vai trò của Đảng với quân đội của Kim Jong-un bằng cuộc thanh trừ Ri Yong Ho. Theo các chuyên gia, nhiều tướng lĩnh quân đội không phục Choe Ryong-hae. Trên thực tế, cuộc thanh trừng Tổng tham mưu trưởng quân đội Ri Yong-ho là do phía Đảng Lao động tiến hành chứ không phải quân đội dưới sự chỉ đạo của Choe Ryong-hae.[2]

Tháng 12 năm 2012 ông bị giáng quân hàm xuống Đại tướng, khi ông mặc bộ quân phục mang hàm tướng tại lễ kỷ niệm 1 năm ngày mất Kim Jong-il tại cung Kumsusan. Mặc dù trong ngày 14/12/2012 ông vẫn mặc quân phục cấp Phó Soái tại cuộc phóng tên lửa Quang Minh Tinh 3.Đồng thời Hyon Yong-chol cũng bị giáng xuống còn cấp tướng và việc cắt chức Bộ trưởng Bộ Lực lượng Vũ trang Nhân dân Kim Jong-Gak càng gia tăng sự bất mãn với Choe Ryong-hae.

Tại lễ kỷ niệm 50 Kim Nhật Thành ra khẩu hiệu, 5 tháng 2 năm 2013 Choe Ryong-hae đã mặc quân hàm cấp Phó Soái cho thấy đây là sự thăng cấp của ông.[3] Ngày 22 tháng 5 năm 2013 ông là đặc phái viên của Kim Jong-un đến thăm Trung Quốc.[4]